package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.ListNode;

import java.util.*;

/**
 * 从链表中移除节点
 * https://leetcode.cn/problems/remove-nodes-from-linked-list/
 *
 * @time 2024/1/3
 */
public class RemoveNodes {

//    public static void main(String[] args) {
////        ListNode l1 = new ListNode(5);
////        ListNode l2 = new ListNode(2);
////        ListNode l3 = new ListNode(13);
////        ListNode l4 = new ListNode(14);
////        ListNode l5 = new ListNode(8);
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(1);
//        ListNode l4 = new ListNode(1);
//        ListNode l5 = new ListNode(1);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//
//        RemoveNodes rn = new RemoveNodes();
//        ListNode newHead = rn.removeNodes(l1);
//        System.out.println();
//    }


    public ListNode removeNodes(ListNode head) {
        Queue<Node> queue = toQueue(head);
        ListNode tmp = head, newHead = null, lastNode = null;
        int[] already = new int[queue.size()];
        int index = 0;
        while (tmp != null) {

            while (!queue.isEmpty() && already[queue.peek().index] == 1) {
                queue.poll();
            }
            Node peek = queue.peek();
            if (peek.val == tmp.val) {
                if (newHead == null) {
                    newHead = tmp;
                    lastNode = tmp;
                } else {
                    lastNode.next = tmp;
                    lastNode = tmp;
                }
                queue.poll();
            }
            already[index] = 1;
            tmp = tmp.next;
            index++;
        }
        return newHead;
    }

    static class Node {
        private int index;
        private int val;

        public Node(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }

    private Queue<Node> toQueue(ListNode head) {
        Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.val == o2.val) {
                    return o1.index - o2.index;
                }
                return o2.val - o1.val;
            }
        });
        ListNode tmp = head;
        int index = 0;
        while (tmp != null) {
            queue.add(new Node(index++, tmp.val));
            tmp = tmp.next;
        }
        return queue;
    }
}
